package subject_set.offer100;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author haomin
 * @date 2022/10/21 17:06
 **/
public class Offer48 {
    class Solution {
        public int lengthOfLongestSubstring(String s) {
            Map<Character,Integer> map = new HashMap<>();
            int max = 0, start = 0;
            for(int i = 0; i < s.length(); ++i){
                char c = s.charAt(i);
                if(map.containsKey(c)){
                    start = Math.max(start, map.get(c) + 1); // start 从重复位的下一个位置开始
                }
                max = Math.max(i - start + 1, max);
                map.put(c, i); // 如果相同，更新坐标
            }
            return max;
        }
    }

    class Solution2 {
        public int lengthOfLongestSubstring(String s) {
            Set<Character> set = new HashSet<>();
            int max = 0;
            for(int l = 0, r = 0; r < s.length(); ++r){
                char c = s.charAt(r);
                while(set.contains(c)){
                    set.remove(s.charAt(l));
                    l++;
                }
                set.add(c);
                max = Math.max(max, r - l + 1);
            }
            return max;
        }
    }
}